#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int cmp(int* p1, int* p2) {
    return *p1 - *p2;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), cmp);
    *returnSize = 0;
    if (numsSize < 4)
        return NULL;
    int** ans = (int**)malloc(sizeof(int*) * 1001);
    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1])continue;
        if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)break;
        if ((long long)nums[i] + nums[numsSize - 1] + nums[numsSize - 2] + nums[numsSize - 3] < target)continue;
        int T = target - nums[i];
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1])continue;
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                long long sum = (long long)nums[j] + nums[left] + nums[right];
                if (sum == T) {
                    int* tmp = (int*)malloc(sizeof(int) * 4);
                    tmp[0] = nums[i];
                    tmp[1] = nums[j];
                    tmp[2] = nums[left];
                    tmp[3] = nums[right];
                    ans[(*returnSize)++] = tmp;
                    while (left < right && nums[left] == nums[++left]);
                    while (left < right && nums[right] == nums[--right]);
                }
                if (sum < T) {
                    while (left < right && nums[left] == nums[++left]);
                }
                if (sum > T) {
                    while (left < right && nums[right] == nums[--right]);
                }
            }
        }
    }
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 4;
    }
    return ans;
}